import sys


class Graph():
    def __init__(self, Vertices):
        self.V = Vertices
        self.graph = [[0 for _ in range(Vertices)] for _ in range(Vertices)]


    def minDistance(self, dist,PassedPath):
        min_dist = sys.maxsize

        for i in range(self.V):
            if dist[i] < min_dist and PassedPath[i] == False:
                min_dist = dist[i]
                min_index = i

        return min_index
    def printSolution(self, dist):

        print("Vertex tDistance from Source")

        for node in range(self.V):
            print(node, "t", dist[node])
    def dijkstra(self, start):
        dist = [sys.maxsize] * self.V
        dist[start] = 0
        PassedPath=[False for _ in range(self.V)]
        for _ in range(self.V):
            u = self.minDistance(dist,PassedPath)
            PassedPath[u] = True
            for v in range(self.V):
                if self.graph[u][v] > 0 and PassedPath[v] == False and \
                        dist[v] > self.graph[u][v] + dist[u]:
                    dist[v] = self.graph[u][v] + dist[u]

        self.printSolution(dist)

class Graph1():

    def __init__(self, vertices):

        self.V = vertices

        self.graph = [[0 for column in range(vertices)]

                      for row in range(vertices)]

        print(self.graph)
    def printSolution(self, dist):

        print("Vertex tDistance from Source")

        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

        for v in range(self.V):

            if dist[v] < min and sptSet[v] == False:
                min = dist[v]

                min_index = v

        return min_index

    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V

        dist[src] = 0

        sptSet = [False] * self.V

        for cout in range(self.V):
            u = self.minDistance(dist, sptSet)
            sptSet[u] = True
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)


# Driver program
if __name__ == "__main__":
    g = Graph(9)

    g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

               [4, 0, 8, 0, 0, 0, 0, 11, 0],

               [0, 8, 0, 7, 0, 4, 0, 0, 2],

               [0, 0, 7, 0, 9, 14, 0, 0, 0],

               [0, 0, 0, 9, 0, 10, 0, 0, 0],

               [0, 0, 4, 14, 10, 0, 2, 0, 0],

               [0, 0, 0, 0, 0, 2, 0, 1, 6],

               [8, 11, 0, 0, 0, 0, 1, 0, 7],

               [0, 0, 2, 0, 0, 0, 6, 7, 0]

               ]

    print(g.dijkstra(0))

# This code
